package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

/**
https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/?envType=problem-list-v2&envId=binary-tree

103. 二叉树的锯齿形层序遍历
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

[tree1.jpg](https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg)

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]
 */
class leetcode_103 {

    @Test
    fun test_1() {
        val n3 = TreeNode(3)
        val n9 = TreeNode(9)
        val n20 = TreeNode(20)
        val n15 = TreeNode(15)
        val n7 = TreeNode(7)
        n3.left = n9
        n3.right = n20
        n20.left = n15
        n20.right = n7

        val actual = zigzagLevelOrder(n3)
        val expected = arrayListOf(arrayListOf(3), arrayListOf(20, 9), arrayListOf(15, 7))
        Assert.assertEquals(expected.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val actual = zigzagLevelOrder(n1)
        val expected = arrayListOf(arrayListOf(1))
        Assert.assertEquals(expected.toString(), actual.toString())
    }

    @Test
    fun test_3() {
        val actual = zigzagLevelOrder(null)
        val expected = ArrayList<ArrayList<Int>>()
        Assert.assertEquals(expected.toString(), actual.toString())
    }

    private fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {
        /**
         * 思路：层次遍历 - 队列 （Recommend ： 更好理解）
         * 1 正常遍历
         * 2 isOrderLeft 表示收集方向，初始值为左方向，true。
         * 收集节点时，若 isOrderLeft = false，先 reverse 收集节点list，再加入结果集。
         */

        val result: ArrayList<ArrayList<Int>> = ArrayList()
        // 1 终止条件
        if (null == root) {
            return result
        }
        // 2 队列初始化、方向初始化
        val queue: LinkedList<TreeNode> = LinkedList()
        queue.offer(root)
        var isOrderLeft = true

        // 3 外层遍历，以及层的大小
        while (!queue.isEmpty()) {
            var size = queue.size
            val list: ArrayList<Int> = ArrayList()
            // 4 内层遍历
            while (size-- > 0) {
                // 处理节点
                val node: TreeNode = queue.poll()
                list.add(node.`val`)

                node.left?.let {
                    queue.offer(it)
                }
                node.right?.let {
                    queue.offer(it)
                }
            }
            // 收集节点
            if (!isOrderLeft) {
                /**
                list.reverse : 原地反转list
                list.reversed :返回反转的新list，原来list不改变
                 */
                list.reverse()
            }
            isOrderLeft = !isOrderLeft
            result.add(list)
        }
        // 5 返回值
        return result
    }
}